Teorema de Cook

Mira otros diccionarios:

• Teorema de Cook — En teoría de la complejidad computacional, el Teorema de Cook establece lo siguiente: El Problema de satisfacibilidad booleana (SAT) es NP completo. Stephen Cook (1971) Cook demostró este teorema en su artículo de 1971 The Complexity of Theorem… …   Wikipedia Español

• Cook — hace referencia a: James Cook, navegante y descubridor británico; Robin Cook, escritor estadounidense; Islas Cook, archipiélago del Pacífico Sur. Stephen Cook, matemático computacional creador del Teorema de Cook. Cook (perro), perro actor de la… …   Wikipedia Español

• Teorema de la jerarquía temporal — En la teoría de complejidad computacional, los teoremas de jerarquía temporal son declaraciones importantes sobre cómputo de tiempo acotado en máquinas de Turing. Informalmente, estos teoremas dicen que con más tiempo, una máquina de Turing puede …   Wikipedia Español

• NP-completo — En teoría de la complejidad computacional, la clase de complejidad NP completo es el subconjunto de los problemas de decisión en NP tal que todo problema en NP se puede reducir en cada uno de los problemas de NP completo. Se puede decir que los… …   Wikipedia Español

• Leonid Levin — Leonid Anatólievich Levin Леонид Анатольевич Левин (nació el 2 de noviembre de 1948 en la antigua URSS). Es informático, estudió siguiendo los pasos de Andréi Kolmogórov. Leonid obtuvo su primer Doctorado en filosofía en 1972 en la universidad de …   Wikipedia Español

• Problema de satisfacibilidad booleana — Saltar a navegación, búsqueda En teoría de la complejidad computacional, el Problema de satisfacibilidad booleana (SAT) fue el primer problema identificado como perteneciente a la clase de complejidad NP completo. Se trata de un problema donde… …   Wikipedia Español

• NP (Complejidad computacional) — Saltar a navegación, búsqueda Los recursos comúnmente estudiados en complejidad computacional son: – El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema. – El espacio: mediante… …   Wikipedia Español

• NP (clase de complejidad) — En teoría de la complejidad computacional, NP es el acrónimo en inglés de nondeterministic polynomial time ( tiempo polinomial no determinista ). Es el conjunto de problemas que pueden ser resueltos en tiempo polinómico por una máquina de Turing… …   Wikipedia Español

• Clases de complejidad P y NP — Diagrama de clases de complejidad para el caso en que P ≠ NP. La existencia de problemas fuera tanto de P como de NP completos en este caso fue determinada por Ladner.[1] La relación entre las clases de complejidad P …   Wikipedia Español

• Número áureo — Para el número de astronomía, ver Número áureo (astronomía) El número áureo o de oro (también llamado número plateado, razón extrema y media,[1] razón áurea, razón dorada, media áurea, proporción áurea y divina proporción) representado por la… …   Wikipedia Español